Conventionally, in VICS (a road traffic information communication system), there has been a service of providing road traffic information indicating road segments where traffic jams are occurring or traveling time to vehicular navigation systems which have digital map databases installed therein through FM multiplex broadcasting or beacons. The vehicular navigation system receives the road traffic information to display a colored traffic-jam occurring road segment on a map displayed on the screen or to calculate a required time to a goal point for display.
Thus, when road traffic information is provided, the position information on a road on the digital map needs to be transmitted. In addition, also in a service of providing information on a recommended route which makes it possible to reach a goal point in a shortest time by receiving information on the current point and the goal point or a road traffic information collecting system for which researches have been being made in recent years and in which locus information and speed information are collected from running vehicles (probe cars), the recommended route on the digital map and the traveling path need to be transmitted accurately to a receiving side.
Heretofore, when attempting to transmit road positions on digital maps, link numbers assigned to roads or node numbers which specify nodes such as intersections are used. However, node numbers and link numbers defined for the road network need to be renumbered with new numbers as new roads are built or the existing roads are rerouted, and since digital map data produced by respective map manufacturers also need to be renewed in association with the renumbering of link numbers and node numbers, the methods using the node numbers and link numbers require tremendous social costs for maintenance.
With a view to improving these points, the following patent document No. 1 (JP-A-2003-23357) proposes a method for transmitting a road segment on a digital map without using node numbers and link numbers and in a small volume of data.
In this method, sampling points are reset on a road segment that is attempted to be transmitted at intervals of a constant distance (this being referred to as an equidistance resampling) on a road segment to be transmitted, a compression coding process is applied to a data string in which position data of the respective sampling points are arranged sequentially, and compression encoded data are transmitted. On a receiving side which receives the compression encoded data restores the data string of the position data of the sampling points and implements a map matching of the position data with its own digital map data so as to identify the road segment.
Alternatively, the receiving side decodes the position data of the sampling points and displays a resampling shape in which the sampling points are linked to each other on its own digital map, or, in order to identify the transmitted road segment accurately, implements a map matching of the position data of the sampling points with its own digital map data so as to identify the object road on its digital map data.
The compression encoding of the data string of position data is implemented sequentially as follows: (1) Conversion of position data into single variable; (2) Conversion of a value represented by a single variable into a statistically biased value; and (3) Variable length coding of the converted value.
(1) Conversion of Position Data into Single Variable
FIG. 34A shows sampling points set along the road segment by the equidistant resampling as PJ−1, PJ. The sampling point (PJ) can uniquely be identified in two dimensions of a distance L from the adjacent sampling point (PJ−1) and an angular component Θ, and assuming that the distance is constant (L), the sampling point (PJ) can be represented by one variable of only the angular component Θ from the adjacent sampling point (PJ−1). In FIG. 34A, as this angle Θ, an angle Θ is shown which is represented by an absolute orientation which designates the magnitude in a range of 0 to 360 degrees measured clockwise from the orientation of true north (top on the map) which is regarded as 0 degree. Assuming that the x-y coordinates (latitude, longitude) of PJ−1 and PJ are (xj−1, yj−1) and (xj, yj), respectively, this angle Θj−1 can be calculated from the following equation:Θj−1=tan−1{(xj−xj−1)/(yj−yj−1)}
Consequently, the road segment can be represented by a data string of angular components of the respective sampling points by designating the constant distance L between the sampling points and latitude and longitude of the sampling point (reference point) which constitutes an origin or a destination separately.
(2) Conversion of Single Variable Value into Statistically Biased Value
In order for a single variable value of each sampling point to become a statistically biased value which is suitable for variable length coding, as shown in FIG. 34B, the angular component of each sampling point is represented by a displacement difference from the angular component of the adjacent sampling point, that is, a deviation angle Θj. This deviation angle Θj is calculated as:Θj=Θj−Θj−1In the event that the road is rectilinear, the deviation angle of each sampling point focuses on the vicinity of 0 and becomes statistically biased data.
In addition, as shown in FIG. 34C, the angular component of the sampling point can be converted into statistically biased data by representing the deviation angle θj of the sampling point PJ, to which attention is to be paid, by a difference value (deviation angle estimated difference value) Δθj from a deviation angle estimated value Sj (statistically estimated value) of the sampling point PJ which is estimated using deviation angles θj−1, θj−2, . . . of the previous sampling points PJ−1, PJ−2, . . . . The statistically estimated value Sj can be defined as, for example:Sj=θj−1; orSj=(θj−1+θj−2)/2In addition, Sj may be defined in terms of a weighted average of deviation angles at the n previous sampling points. The deviation angle estimated difference value Δθj is calculated as:Δθj=θj−SjIn the event that the road curves at a constant curvature, a deviation angle estimated difference value Δθ of each sampling point focuses on the vicinity of 0 and becomes statistically biased data.
FIG. 34D is a graph illustrating frequency at which data are generated when a rectilinear road segment is represented by the deviation angle θ and when the curved road segment is represented by the deviation angle estimated difference value Δθ. The generation frequency of θ and Δθ becomes maximum when θ=0° and is statistically biased.
(3) Variable Length Coding
Next, the value of the data string which is converted into the statistically biased value is variable length coded. While the variable length coding method includes many types of methods such as fixed numerical value compression method (0 compression or the like), Shannon-Fanno coding method, Huffman coding method, arithmetic coding method and lexicographic coding method, and any method may be usede.
Here a case will be described in which Huffman coding method, which is the commonest, is used.
In this variable length coding, more frequently generated data are coded by bits in a smaller number and less frequently generated data are coded by bits in a greater number, so that the total data volume is reduced. A relationship between the data and codes are defined in a code table.
Now, assume that the arrangement of Δθs at sampling points along the recommended route which are represented in a unit of 1° is as follows:
“0—0—−2—0—0—+1—0—0—−1—0—+5—0—0—0—+1—0”
A case will be described where a code table shown in FIG. 35 in which variable length coding and run length coding are combined is used in order to code the data string. In this code table, a minimum angular resolution (δ) is set to 3°, and the code table regulates such that Δθ which is in the range of −1° to +1° is regarded as 0° and is then represented by a code 0, in a case where 0° occurs continuously five times, it is represented by a code 100, and in a case where 0° occurs continuously ten times, it is represented by a code 1101. In addition, Δθ which is in the range of +/−2° to 4° is regarded as +/−3° and when it is positive, Δθ is then represented by adding an additional bit 0 to a code 1110, whereas when it is negative, Δθ is then represented by adding an additional bit 1 to the code 1110, Δθ which is in the range of +/−5° to 7° is regarded as +/−6° and is then represented by adding an additional bit denoting positive or negative to a code 111100, and Δθ which is in the range of +/−8° to 10° is regarded as +/−9° and is then represented by adding an additional bit denoting positive or negative to a code 111101.
Due to this, the data string is coded as follows:
“0—0—11101—100—0—0—1111000—100”→“0011101100001111000100”
The receiving side which has received the data restores the data string of Δθs using the same code table as that used in coding and reproduces the position data of the sampling points by implementing an opposite process to that implemented on a transmitting side.
Thus, the volume of data to be transmitted can be reduced by coding the same.
In addition, the patent document No. 1 proposes that the constant distance L in the equidistance resampling be set by paying attention to the magnitude of the curvature of the shape of a road. Namely, when performing the resampling on an object road which has a large curvature and hence is curved or in a mountainous area where there are many such roads, the distance L in the equidistance resampling is set short, whereas when performing the resampling on an object road which has a small curvature and hence is rectilinear or in an urban area where there are many such roads, the distance L is set longer. This is because in the event that the resampling is performed on a road which is largely curved using the distance which is long, sampling points cannot be disposed at positions indicating the characteristic shape of the road, whereby the occurrence of erroneous matching on the receiving side becomes highly possible.
In the conventional resampling method, however, since sampling points are set such that the distance error from the shape of a road (original shape data) that is to be transmitted becomes as small as possible, as shown FIGS. 15A, 15B, when original shape data (dotted lines) curves clockwise or counterclockwise, resampling shapes (solid lines) which link sampling points take shapes which are positioned slightly close to the centers of the curves. The dissociation between the resampling shape and the original shape is increased as the resampling length becomes longer. Due to this, when attempting to reduce the dissociation, the resampling length has to be set shorter, however, in the event that the attempt is actually done, the volume of data to be transmitted is increased. Moreover, even in the event that the resampling distance is set as short as possible, it is theoretically not possible to eliminate the dissociation completely.
Furthermore, in order to transmit the shape of a road on the digital map, in a case where angle components indicating the positions of sampling points are represented by angle resolutions δ (namely, quantized in a unit of δ) and are compression coded for transmission, the following problems exist.    {circle around (1)} The data volume of the angle component can be reduced by setting a large angle resolution δ (namely, by setting a large quantization unit). In the above explanation, while δ=3° is illustrated as an example, in case δ=6°, the data volume can further be reduced. In the event that a large angle resolution δ is set, however, the quantization error becomes larger, the occurrence of erroneous matching on the receiving side becomes highly possible.
For example, as shown in FIG. 36, when a point PJ is resampled at a position which is a distance L away from a point PJ−1, assuming that the angle resolution is δ, an angle between a first candidate point P′J for the point PJ and a second candidate point P″J therefor, which is adjacent, becomes δ. Of these, since the candidate point P′J which is closer to the road shape is selected as a sampling point, a distance Ea (namely, an error) between the sampling point and the road shape is expressed as:
Maximum value of Error Ea≈L×|sin(δ/2)|
The greater the angle resolution δ becomes, the greater the error Ea becomes, and the occurrence of erroneous matching on the receiving side becomes highly possible.
Due to this, it is required that the resampling is carried out such that the data volume becomes small and the error from the road shape also becomes small.    {circle around (2)} When the angle component indicating the position of a sampling point is quantized in a unit δ, as shown in FIG. 37, in the event that a sampling point PJ deviates from a rectilinear road for some reason, the next sampling point PJ+1 attempts to compensate for the deviation from the shape of the road in the unit δ and is, as a result, resampled in a state in which it deviates from the road to an opposite side, and this is repeated, whereby there is resulting from the resampling a phenomenon in which the sampling points are disposed in a zigzag fashion.
This zigzag phenomenon prevents the accurate transmission of the road shape to the receiving side and reduces the compression coefficient of data.    {circle around (3)} When the shape of a road is represented by the deviation angles of sampling points or deviation angle estimated difference values for transmission, in the event that the deviation angles indicating the positions of the sampling points or deviation angle estimated difference values are quantized after the rectilinear shape of the road has been resampled, since an error produced by the quantization has an effect on later orientations, there may occur a case where a shape that is reproduced on the receiving side largely deviates from the original shape.